import java.util.Arrays;

public class MaxHeap {
    int[] maxHeap;
    int headpSize;
    static int DEFAULT = 10;
    int UsedSize;
    public MaxHeap(){
        this(10);

    }
    public MaxHeap(int heapSize){
        this.headpSize = heapSize;
        maxHeap = new int[heapSize+1];
    }
    public void add(int element){
        check();
        maxHeap[++UsedSize] = element;
        shiftUp();
    }
    private void check(){
        if(UsedSize==headpSize){
            maxHeap = Arrays.copyOf(maxHeap,2*headpSize);
            headpSize*=2;
        }
    }
    private void shiftUp(){
        int child = UsedSize;
        int parent = child/2;
        while(maxHeap[child]>maxHeap[parent] && child>1){
            swap(maxHeap,child,parent);
            child = parent;
            parent = child / 2;
        }
    }
    public int peek(){
        return maxHeap[1];
    }
    public int pop(){
        if(isEmpty()){
            return Integer.MIN_VALUE;
        }
        int tem = maxHeap[1];
        maxHeap[1] = maxHeap[UsedSize];
        UsedSize--;
        shiftDown();
        return tem;
    }
    private void shiftDown(){
        int index = 1;
        while(index<UsedSize && index<=UsedSize/2){
            int target = maxHeap[index*2]>maxHeap[index*2+1] ? index*2 : index*2+1;
            if(maxHeap[index]<maxHeap[target]){
                swap(maxHeap,index,target);
            }else{
                break;
            }
        }
    }
    private void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
    public boolean isEmpty(){
        return UsedSize==0;
    }
    public int size(){
        return UsedSize;
    }
    public String toString() {
        if (UsedSize == 0) {
            return "No element!";
        } else {
            StringBuilder sb = new StringBuilder();
            sb.append('[');
            for (int i = 1; i <= UsedSize; i++) {
                sb.append(maxHeap[i]);
                sb.append(',');
            }
            sb.deleteCharAt(sb.length() - 1);
            sb.append(']');
            return sb.toString();
        }
    }

    }



